package Euler31;

import java.util.*;

public class CoinSums {
	public static void main(String[] args) {
		//final int[] coins = {200, 100, 50, 20, 10, 5, 2, 1};
		final int[] coins = {5, 2, 1};
		
		System.out.println(countChanges(10, coins));
	}
	
	private static long countChanges(int amount, int[] coins){
        final int n = coins.length;
        int cycle = 0;
        for (int c : coins)
            if (c <= amount && c >= cycle)
                cycle = c + 1;
        cycle *= n;
        long[] table = new long[cycle];
        Arrays.fill(table, 0, n, 1);
        Arrays.fill(table, n, cycle, 0);
 
        int pos = n;
        for (int s = 1; s <= amount; s++) {
            for (int i = 0; i < n; i++) {
                if (i == 0 && pos >= cycle)
                    pos = 0;
                if (coins[i] <= s) {
                    final int q = pos - (coins[i] * n);
                    table[pos] = (q >= 0) ? table[q] : table[q + cycle];
                }
                if (i != 0)
                    table[pos] = table[pos] + table[pos - 1];
                pos++;
            }
        }
 
        return table[pos - 1];
    }
}
